package com.dh.offer;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _4_er_wei_shu_zu_zhong_de_cha_zhao_lcof
 * @Description: 剑指 Offer 04. 二维数组中的查找
 * <p>
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 * 示例:
 * <p>
 * 现有矩阵 matrix 如下：
 * <p>
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * <p>
 * 给定 target = 20，返回 false。
 * <p>
 *  
 * <p>
 * 限制：
 * <p>
 * 0 <= n <= 1000
 * <p>
 * 0 <= m <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2020/12/2 11:02
 */
public class _4_er_wei_shu_zu_zhong_de_cha_zhao_lcof {

    /**
     * 相对于一维数组的二分，这种特性的二维每次分掉一片
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray2(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int xleft = 0;
        int xright = matrix[0].length - 1;
        int yleft = 0;
        int yright = matrix.length - 1;
        while (xleft <= xright && yleft <= yright) {
            int midX = xleft + (xright - xleft + 1) / 2;
            int midY = yleft + (yright - yleft + 1) / 2;
            if (matrix[midY][midX] == target) {
                return true;
            } else if (matrix[midY][midX] < target) {
                if (xright != 0) {
                    xleft = midX + 1;
                } else {
                    yleft = midY + 1;
                }
            } else if (matrix[midY][midX] > target) {
                if (xright != 0) {
                    xright = midX - 1;
                    yright = midY;
                } else {
                    yright = midY - 1;
                    xright = midX;
                }
            }

        }
        return false;
    }

    //看题解的，从左上角开始
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int yl = matrix.length;
        if (yl == 0) {
            return false;
        }
        int xl = matrix[0].length - 1;
        int j = 0;
        while (xl >= 0 && j < yl) {
            int v = matrix[j][xl];
            if (v == target) {
                return true;
            }
            //left
            if (v > target) {
                xl--;
            } else {
                j++;
            }
        }
        return false;
    }


    @Test
    public void findNumberIn2DArrayTest() {


        int[][] matrix = new int[][]{{1, 4}, {2, 5}};

        Assert.assertEquals(true, findNumberIn2DArray(matrix, 4));
        matrix = new int[][]{{1}, {3}, {5}};

        Assert.assertEquals(true, findNumberIn2DArray(matrix, 5));

        matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 5));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 20));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 8));

        matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
        };
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 5));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 19));


        matrix = new int[][]{
                {1, 4, 7, 11, 15},
        };
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 0));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 1));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 7));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 15));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 6));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 78));
        matrix = new int[][]{
                {1}, {2}, {3}, {10}, {18},
        };
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 0));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 1));
        Assert.assertEquals(true, findNumberIn2DArray(matrix, 2));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 7));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 6));
        Assert.assertEquals(false, findNumberIn2DArray(matrix, 78));
    }
}
